#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import defaultdict


class TransferTable:
    # def __init__(self, transfer_map):
    #     self.tm = transfer_map

    def __init__(self, transfer_table):
        self.tm = defaultdict()

        for one_line_transfer in transfer_table:
            state, symbol, new_state = one_line_transfer
            # self.tm.add(state, symbol, new_state)
            self.add(state, symbol, new_state)

    def find(self, state, symbol):
        return self.tm.get(state, {}).get(symbol, None)

    def add(self, state, symbol, new_state):
        self.tm[state] = self.tm.get(state, {})     # 考虑到state不存在的情况
        self.tm[state][symbol] = new_state

    def states(self):
        return self.tm.keys()


class DFA:
    def __init__(self, transfer_table, start_state, accept_states):
        self.tf    = transfer_table
        self.start = start_state
        self.accepts  = accept_states

        self.alphabeta = {'0', '1'}
        self.cur = start_state

    def recognise(self, string):
        self.cur = self.start       # NOTE: 记得初始化cur, 使得recognise()可以重复使用

        for c in string:
            self.cur = self.tf.find(self.cur, c)
            if not self.cur:
                break

            # print('go to %s by %s' % (self.cur, c))

        if not self.cur:
            return False

        # print('last state is ', self.cur)
        return self.cur in self.accepts

    def states(self):
        return self.tf.tm.keys()

    def completement(self):
        # self.tf    = transfer_table
        # self.start = start_state
        # self.accepts  = accept_states
        states = self.states()

        new_ends = set()

        for st in states:
            if st not in self.accepts:
                new_ends.add(st)

        return DFA(self.tf, self.start, new_ends)

    def union(self, other_fsm):
        tt1 = self.tf
        tt2 = other_fsm.tf

        states1 = tt1.tm.keys()
        states2 = tt2.tm.keys()

        merge_transfer_table, merge_start = merge_transfer_and_start(tt1, tt2, self.start, other_fsm.start)
        merge_ends = union_ends(states1, states2, self.accepts, other_fsm.accepts)

        fsm = DFA(merge_transfer_table, merge_start, merge_ends)
        return fsm

    def intersect(self, other_fsm):
        tt1 = self.tf
        tt2 = other_fsm.tf

        states1 = tt1.tm.keys()
        states2 = tt2.tm.keys()

        merge_transfer_table, merge_start = merge_transfer_and_start(tt1, tt2, self.start, other_fsm.start)
        merge_ends = intersect_ends(self.accepts, other_fsm.accepts)

        fsm = DFA(merge_transfer_table, merge_start, merge_ends)
        return fsm

    def equal(self, other_fsm):
        # 判断两个fsm是否相同
        self_complement = self.completement()
        other_complement = other_fsm.completement()

        inter1 = self.intersect(other_complement)
        inter2 = other_fsm.intersect(self_complement)

        return inter1.union(inter2).language_empty()

    def language_empty(self):
        # 是否recognize的字符串都是 empty
        # 使用广度或者深度遍历, 判断是否能到达accepts?
        if not self.accepts:
            return True

        if self.start in self.accepts:
            return False

        # TODO bfa遍历
        queue = [self.start]
        visited = set()
        while queue:
            state = queue.pop()

            if state in visited:
                continue

            visited.add(state)

            for c in self.alphabeta:
                new_st = self.tf.find(state, c)
                queue.append(new_st)

                if new_st in self.accepts:
                    return False

        return True

def union_ends(states1, states2, ends1, ends2):
    merge_ends = set()
    for first in states1:
        for e2 in ends2:
            merge_ends.add( first+e2 )

    for second in states2:
        for e1 in ends1:
            merge_ends.add( e1+second )

    return merge_ends

# def intersect_ends(states1, states2, ends1, ends2):
def intersect_ends(ends1, ends2):
    merge_ends = set()
    for e1 in ends1:
        for e2 in ends2:
            merge_ends.add( e1+e2 )

    return merge_ends

# def merge_transfer_and_start(t1, t2, start1, start2):
def merge_transfer_and_start(tt1, tt2, start1, start2):
    # tt1 = TransferTable(t1)
    # tt2 = TransferTable(t2)

    states1 = tt1.tm.keys()
    states2 = tt2.tm.keys()

    ttm = []

    # print(states1)
    # print(states2)

    # 1: 对first和second中的state做笛卡尔积: 求得union dfa的所有状态
    # 2: 对union dfa中的每个状态, 计算状态转移(dfa的每个状态针对每个alphabeta中的字母/元素, 都要有转移)
    for first in states1:
        for second in states2:
            for symbol in ['0', '1']:
                # print(first, second, symbol)
                reach1 = tt1.find(first, symbol)
                reach2 = tt2.find(second, symbol)
                ttm.append([first+second, symbol, reach1+reach2])

    merge_transfer_table = TransferTable(ttm)

    merge_start = start1+start2

    return merge_transfer_table, merge_start

# def union(t1, t2, start1, start2, ends1, ends2):
#     tt1 = TransferTable(t1)
#     tt2 = TransferTable(t2)

#     states1 = tt1.tm.keys()
#     states2 = tt2.tm.keys()

#     merge_transfer_table, merge_start = merge_transfer_and_start(t1, t2, start1, start2)
#     merge_ends = union_ends(states1, states2, ends1, ends2)

#     fsm = DFA(merge_transfer_table, merge_start, merge_ends)
#     return fsm

# # def intersect(t1, t2, start1, start2, ends1, ends2):
# #     tt1 = TransferTable(t1)
# #     tt2 = TransferTable(t2)

# #     states1 = tt1.tm.keys()
# #     states2 = tt2.tm.keys()

# #     merge_transfer_table, merge_start = merge_transfer_and_start(t1, t2, start1, start2)
# #     merge_ends = intersect_ends(ends1, ends2)

# #     fsm = DFA(merge_transfer_table, merge_start, merge_ends)
# #     return fsm

